<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 背包理论基础,语雀记录了笔记：https://www.yuque.com/xiaohangge/gb1rvi/hliixt#I0LoU
        let input = [
            '3 4',
            '1 3 4',
            '15 20 25',
        ]
        let main = (input) => {
            // m物品的种类
            // 1背包的容量
            const [n , bagWeight] = input[0].split(' ').map(Number)
            // 第一行物品的重量
            const weight = input[1].split(' ').map(Number)
            // 第二行物品的价值
            const value = input[2].split(' ').map(Number)

            // 初始化，错误，都指向了new Array(bagWeight + 1)这个数组
            // let dp = new Array(n).fill(new Array(bagWeight + 1))
            // 初始化方法1
            // let dp = Array.from({length: n}, () => new Array(bagWeight + 1).fill(0))
            // 初始化方法2
            let dp = new Array(n)
            for (let i = 0; i < n; i++) {
                dp[i] = new Array(bagWeight + 1).fill(0)
            }
            // 第一行
            for (let j = weight[0]; j <= bagWeight; j++) {
                dp[0][j] = value[0]
            }
            for (let i = 1; i < n; i++) {
                for (let j = 1; j <= bagWeight; j++) {
                    // 如果当前背包重量j小于当前物品的重量，放不进去，用上一个的数量
                    if (j < weight[i]) {
                        dp[i][j] = dp[i - 1][j]
                    } else {
                        // 否则，根据递推公式来，来自左上方的值
                        // i - 1表示从0->i的物品挑选，j-weight[i]表示要放第i个物品，必须腾出weight[i]的重量
                        dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j])
                    }
                }
            }
            return dp[n - 1][bagWeight]
        }
        console.log(main(input), 'main(input)');
    </script>
</body>

</html>